package com.hyb.algorithm.data.struct.other;

/**
 * @author: ybhu
 * @create: 2021/09/19 21:03
 *
 * 283. 移动零
 * https://leetcode-cn.com/problems/move-zeroes/
 */
public class MoveZeroes {


    public void moveZeroes(int[] nums) {
        int n=nums.length;
        int j=0;
        for(int i=0;i<n;i++){
            if(nums[i]!=0){
                if(i!=j){
                    nums[j]=nums[i];
                }
                j++;
            }
        }

        for(int i=j;i<n;i++){
            nums[i]=0;
        }
    }


    //时间复杂度O（n）
    //空间复杂度O(1)
    public void moveZeroes2(int[] nums) {

        //[0...noZeroIndex)  nums中 0--noZeroIndex  均为非0元素
        int noZeroIndex=0;
        //遍历到第i个元素后，保证[0...i]中的所有非0元素
        //都按照顺序排列在[0...k)
        //同时保证 [k..i] 都是零元素
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                swap(nums,noZeroIndex,i);
                noZeroIndex++;
            }
        }
    }


    private void swap(int[] nums,int source,int target){
        int temp=nums[source];
        nums[source]=nums[target];
        nums[target]=temp;
    }
}
